
class Solution {
public:
    vector<int> v;
    int ret = 0;
    int reversePairs(vector<int>& record) {
        v.resize(record.size());
        Mergesort(record, 0, v.size() - 1);
        return ret;
    }
    void Mergesort(vector<int>& num, int left, int right)
    {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        Mergesort(num, left, mid);
        Mergesort(num, mid + 1, right);
        int cur2 = mid + 1, cur1 = left, i = left;
        while (cur1 <= mid && cur2 <= right)
            v[i++] = num[cur1] > num[cur2] ? ret += right - cur2 + 1, num[cur1++] : num[cur2++];
        while (cur1 <= mid)  v[i++] = num[cur1++];
        while (cur2 <= right) v[i++] = num[cur2++];
        for (int x = left; x <= right; x++)
            num[x] = v[x];
    }
};
class Solution {
public:
    vector<int> v;
    vector<int> _v;
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> _num;
        vector<int> sum;
        v.resize(nums.size());
        _v.resize(nums.size());
        _num.resize(nums.size());
        sum.resize(nums.size());
        for (int x = 0; x < nums.size(); x++)
            _num[x] = x;
        Mergesort(nums, _num, sum, 0, v.size() - 1);
        return sum;
    }

    void Mergesort(vector<int>& num, vector<int>& _num, vector<int>& sum,
        int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        Mergesort(num, _num, sum, left, mid);
        Mergesort(num, _num, sum, mid + 1, right);
        int cur2 = mid + 1, cur1 = left, i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (num[cur1] > num[cur2]) {
                sum[_num[cur1]] += right - cur2 + 1;
                v[i] = num[cur1];
                _v[i++] = _num[cur1++];
            }
            else {
                v[i] = num[cur2];
                _v[i++] = _num[cur2++];
            }
        }
        while (cur1 <= mid) {
            v[i] = num[cur1];
            _v[i++] = _num[cur1++];
        }
        while (cur2 <= right) {
            v[i] = num[cur2];
            _v[i++] = _num[cur2++];
        }

        for (int x = left; x <= right; x++) {
            num[x] = v[x];
            _num[x] = _v[x];
        }
    }
};